package leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0239.java
 * @Author : WangRuoyu
 * @Date 2023/11/9 17:48
 */


public class Q0239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        ArrayList<Integer> q = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i >= k && q.get(0) <= i - k) {
                q.remove(0);
            }
            while (!q.isEmpty() && nums[q.get(q.size() - 1)] <= nums[i]) {
                q.remove(q.size() - 1);
            }
            q.add(i);
            if (i >= k - 1) {
                res[i - k + 1] = nums[q.get(0)];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Q0239 sl = new Q0239();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(sl.maxSlidingWindow(nums, k)));
    }
}